package JZ_Offer.algorithm.backtracking;

/**
 * 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，
 * 但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。
 * 但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
 */
public class JZ13_机器人的运动范围 {
    // 统计能够走到的次数
    private int count = 0;

    private int movingCount(int threshold, int rows, int cols) {
        countRec(0, 0, rows, cols, threshold, new int[rows][cols]);
        return count;
    }

    private void countRec(int row, int col, int rows, int cols, int threshold, int[][] flag) {
        if (row >= rows || col >= cols) {
            return;
        }

        // 无论是广度优先遍历还是深度优先遍历，我们一定要知道的时候遍历一定会有终止条件也就是要能够停止，
        // 不然程序就会陷入死循环，这个一定是我们做此类题目必须要注意的地方
        if (flag[row][col] == 1) {
            return;
        }

        if (isValid(row, col, threshold)) {
            return;
        }

        // 标记访问过
        flag[row][col] = 1;

        count++;
        countRec(row + 1, col, rows, cols, threshold, flag);
        countRec(row, col + 1, rows, cols, threshold, flag);
    }

    // 判断坐标是否符合要求
    private boolean isValid(int row, int col, int threshold) {
        int sum = 0;
        while (row > 0) {
            sum += row % 10;
            row = row / 10;
        }
        while (col > 0) {
            sum += col % 10;
            col = col / 10;
        }
        return sum > threshold;
    }

    // 判断坐标是否符合要求(效率较差)
    private boolean isValid1(int row, int col, int threshold) {
        int sum = 0;
        char[] r = String.valueOf(row).toCharArray();
        char[] c = String.valueOf(col).toCharArray();
        for (int i = 0; i < r.length; i++) {
            sum += r[i] - '0';
        }
        for (int i = 0; i < c.length; i++) {
            sum += c[i] - '0';
        }
        return sum > threshold;
    }

    public static void main(String[] args) {
        JZ13_机器人的运动范围 main = new JZ13_机器人的运动范围();
        long mi = System.nanoTime();
        int count = main.movingCount(10, 30, 30);
        System.out.println(System.nanoTime() - mi);
        System.out.println(count);
    }

}
